package leetcode.code1976;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int mod = (int) 1e9 + 7;

	public int countPaths(int n, int[][] roads) {
		// 两点之间耗时
		int[][] edgeValues = new int[n][n];
		// 邻接点
		List<Integer>[] nexts = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < roads.length; i++) {
			int[] road = roads[i];
			int ui = road[0], vi = road[1], timei = road[2];
			// 双向权重一致，耗时
			edgeValues[ui][vi] = timei;
			edgeValues[vi][ui] = timei;
			// 邻接点
			nexts[ui].add(vi);
			nexts[vi].add(ui);
		}
		// 抵达点的最小耗时
		long[] minCost = new long[n];
		Arrays.fill(minCost, Long.MAX_VALUE);
		minCost[0] = 0;
		// 抵达点的最小耗时对应的方法数
		long[] minWay = new long[n];
		minWay[0] = 1;
		// 优先决定权重最小的点向下移动
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		queue.add(new int[] { 0, 0 });
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int u = cur[0], cost = cur[1];
			long way = minWay[u];
			// 当前耗时是最小，确实是这个点移动
			if (minCost[u] == cost) {
				// u的邻接点v们
				List<Integer> next = nexts[u];
				for (int i = 0; i < next.size(); i++) {
					// 检查一个邻接点v
					int v = next.get(i);
					int time = edgeValues[u][v];
					int nextCost = cost + time;
					// 耗时比之前抵达的耗时小，说明有更优路径，同时保证不走回头路（来时的耗时一定更小）
					if (nextCost < minCost[v]) {
						minCost[v] = nextCost;// 更新最小耗时
						minWay[v] = way;// 抵达v的方法数等同于到达u的方法数
						queue.add(new int[] { v, nextCost });// 添加优先决策，可能有v，但是cost更大，后续poll出来比较minCost的时候就过滤掉了
					} else if (nextCost == minCost[v]) {
						// 耗时相等，累加方法数
						minWay[v] += way;
					}
					minWay[v] %= mod;
				}
			}
		}
		return (int) minWay[n - 1];
	}

	@Override
	public void debug4() {
		H.compare(4, this.countPaths(7,
				H.str2array1("[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]")));
		H.compare(1, this.countPaths(7, H.str2array1(
				"[[0,6,107],[0,1,2],[1,2,3],[1,3,103],[6,3,3],[3,5,1],[6,5,108],[2,5,1],[0,4,105],[4,6,2]]")));

	}

	@Override
	public void debug3() {

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
